% Aufgaben Lösungen.tex
\documentclass{article}

\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage[T1]{fontenc}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii})}


\begin{document}
Aufgabe 3.2.2:\\
\\
Die Übergangstabelle eines DEA siehe wie folgt aus:\\

%\begin{center}
%--------------------------------------------
\begin{tabular}{c|l|l|}
|                     & 0       & 1         \\
\hline \hline

$\rightarrow q_{1}$   & $q_{2}$ & $q_{3}$   \\

$q_{2}$               & $q_{1}$ & $q_{3}$   \\

$^{\ast}q_{3}$        & $q_{2}$ & $q_{1}$		\\
\hline

\end{tabular}
%--------------------------------------------
\\
\\
Die Graph eines DEA sehe wie folgt aus:




\begin{center}
%-----------------------------------------------------------------------------------------------------------
    \unitlength=4pt
    \begin{picture}(20, 14)(0,-7)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    %\node[Nmarks=ifr](C)(75,-30){all}
    \node[Nmarks=i,iangle=180](A1)(-20,0){$q_{1}$}
    \node(A2)(0,0){$q_{2}$}
    \node[Nmarks=r](A3)(20,0){$q_{3}$}
    \drawedge(A1,A2){$0$}
    \drawedge(A2,A1){$0$}
    \drawedge(A2,A3){$1$}
    \drawedge(A3,A2){$0$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(A1,A3){$1$}
    \drawedge(A3,A1){$1$}
    %\drawloop[loopangle=90](A1){$1$}
    %\drawloop[loopangle=0](A3){$0$}
    \end{picture}
%----------------------------------
\end{center}

\begin{enumerate}
	\item Formulieren Sie alle regulären Ausdrücke $R^{(0)}_{ij}$. \textit{Hinweis:} Stellen Sie sich den Zustand $q_{i}$ so vor, als 					handle es sich um den Zustand mit der ganzzahligen Nummer $i$.
	\item Formulieren Sie alle regulären Ausdrücke $R^{(1)}_{ij}$. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.
	\item Formulieren Sie alle regulären Ausdrücke $R^{(2)}_{ij}$. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.
	\item Formulieren Sie einen regulären Ausdruck für die Sprache des Automaten.
	\item Konstruieren Sie das Übergangsdiagramm für den DEA, und geben sie einen regulären Ausdruck für die Sprache des Automaten an, 					indem sie $q_{2}$ eleminieren.
\end{enumerate}

\textbf{Lösung:}

\begin{enumerate}%enumeration für a) b) c) ...
	\item%Lösung zu Aufgabe a)
		Analog zu Aufgabe 3.2.1 werden nun alle $R^{(0)}_{ij}$  für alle  $i,j \in \{1,2,3\}$ bestimmt. Zur Verkürzung wird hier auf längere Erklärungen 				verzichtet:
	\begin{enumerate}%enumeration für 1) 2) ....
		\item $R^{(0)}_{11} = \varepsilon$
		\item $R^{(0)}_{12} = 0$
		\item $R^{(0)}_{13} = 1$
		\item $R^{(0)}_{21} = 0$
		\item $R^{(0)}_{22} = \varepsilon$
		\item $R^{(0)}_{23} = 1$
		\item $R^{(0)}_{31} = 1$
		\item $R^{(0)}_{32} = 0$
		\item $R^{(0)}_{33} = \varepsilon$
	\end{enumerate}%enumeration für 1) 2) ....
	\item%Lösung zu Aufgabe b)
			Analog zu Aufgabe 3.2.1 werden nun aus den $R^{(0)}_{ij}$ alle $R^{(1)}_{ij}$ gebildet mit 
			$R^{(k)}_{ij} = R^{(k-1)}_{ij} + R^{(k-1)}_{ik} (R^{(k-1)}_{kk})^{\ast} R^{(k-1)}_{kj}$:
	\begin{enumerate}%1) 2) ....
		\item 
		\begin{tabbing}
		$R^{(1)}_{11}$\=$=R^{(1-1)}_{11} + R^{(1-1)}_{11} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{11}$\\
		\>$= \varepsilon + \varepsilon(\varepsilon)^{\ast}\varepsilon$\\
		\>$= \varepsilon$		
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{12}$\=$=R^{(1-1)}_{12} + R^{(1-1)}_{11} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{12}$\\
		\>$= 0 + \varepsilon(\varepsilon)^{\ast}0$\\
		\>$= 0$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{13}$\=$=R^{(1-1)}_{13} + R^{(1-1)}_{11} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
		\>$= 1 + \varepsilon(\varepsilon)^{\ast}1$\\
		\>$= 1$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{21}$\=$=R^{(1-1)}_{21} + R^{(1-1)}_{21} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{11}$\\
		\>$= 0 + 0(\varepsilon)^{\ast}\varepsilon$\\
		\>$= 0$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{22}$\=$=R^{(1-1)}_{22} + R^{(1-1)}_{21} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{12}$\\
		\>$= \varepsilon + 0\varepsilon^{\ast}0$\\
		\>$= \varepsilon + 00$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{23}$\=$=R^{(1-1)}_{23} + R^{(1-1)}_{21} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
		\>$= 1+01$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{31}$\=$=R^{(1-1)}_{31} + R^{(1-1)}_{31} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{11}$\\
		\>$= 1 + 1\varepsilon^{\ast}\varepsilon$\\
		\>$= 1$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{32}$\=$=R^{(1-1)}_{32} + R^{(1-1)}_{31} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{12}$\\
		\>$= 0 + 01$\\
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(1)}_{33}$\=$=R^{(1-1)}_{33} + R^{(1-1)}_{31} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
		\>$= \varepsilon + 11$
		\end{tabbing}
		
	\end{enumerate}%1) 2) ....
	\item%Lösung zu Aufgabe c)
		Analog zu Aufgabe 3.2.1 werden nun aus den $R^{(1)}_{ij}$ alle $R^{(2)}_{ij}$ gebildet mit 
			$R^{(k)}_{ij} = R^{(k-1)}_{ij} + R^{(k-1)}_{ik} (R^{(k-1)}_{kk})^{\ast} R^{(k-1)}_{kj}$:
	\begin{enumerate}%1) 2) ....
		\item
		\begin{tabbing}
		$R^{(2)}_{11}$\=$=R^{(2-1)}_{11} + R^{(2-1)}_{12} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{21}$\\
		\>$\varepsilon + 0(\varepsilon + 00)^{\ast}0$\\
		\>$\varepsilon + 0(00)^{\ast}0$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{12}$\=$=R^{(2-1)}_{12} + R^{(2-1)}_{12} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{22}$\\
		\>$= 0 + 0(\varepsilon + 00)^{\ast}(\varepsilon + 00)$\\
		\>$= 0 + 0(00)^{\ast}$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{13}$\=$=R^{(2-1)}_{13} + R^{(2-1)}_{12} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{23}$\\
		\>$= 1 + 0(00)^{\ast}(1 + 01)$\\
		\>$= 1 + 0(00)^{\ast}1 + 0(00)^{\ast}01$\\
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{21}$\=$=R^{(2-1)}_{21} + R^{(2-1)}_{22} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{21}$\\
		\>$= 0 + (\varepsilon + 00)^{\ast}0$\\
		\>$= 0 + (00)^{\ast}0$\\
		\>$= 0(00)^{\ast}$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{22}$\=$=R^{(2-1)}_{22} + R^{(2-1)}_{22} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{22}$\\
		\>$(\varepsilon + 00) + (\varepsilon + 00)(\varepsilon + 00)^{\ast}(\varepsilon + 00)$\\
		\>$(\varepsilon + 00)^{\ast}$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{23}$\=$=R^{(2-1)}_{23} + R^{(2-1)}_{22} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{23}$\\
		\>$= (1 + 01) + (\varepsilon + 00)(\varepsilon + 00)^{\ast}(1 + 01)$\\
		\>$= (00)^{\ast}(1 + 01)$\\
		\>$= (00)^{\ast}1 + (00)^{\ast}01$
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{31}$\=$=R^{(2-1)}_{31} + R^{(2-1)}_{32} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{21}$\\
		\>$= 1 + (0 + 10)(00)^{\ast}0$\\
		\>$= 1 + 0(00)^{\ast}0 + 10(00)^{\ast}0$\\
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{32}$\=$=R^{(2-1)}_{32} + R^{(2-1)}_{32} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{22}$\\
		\>$= 0 + 01 + (0 + 01)(\varepsilon + 00)^{\ast}(\varepsilon + 00)$\\
		\>$= 0 + 01 + (0 + 01)(00)^{\ast}$\\
		\>$= 0 + 01 + 0(00)^{\ast} + 01(00)^{\ast}$\\
		\>$= 0(00)^{\ast} + 01(00)^{\ast}$\\
		\end{tabbing}
		
		\item
		\begin{tabbing}
		$R^{(2)}_{33}$\=$=R^{(2-1)}_{33} + R^{(2-1)}_{32} (R^{(2-1)}_{22})^{\ast} R^{(2-1)}_{23}$\\
		\>$= \varepsilon + 11 +(0 + 10)(\varepsilon + 00)^{\ast}(1 + 01)$\\
		\>$= \varepsilon + 11 +(0(00)^{\ast} + 10(00)^{\ast})(1 + 01)$\\
		\>$= \varepsilon + 11 + 0(00)^{\ast}1 + 0(00)^{\ast}01 + 10(00)^{\ast}1 + 10(00)^{\ast}01$
		\end{tabbing} 
	
	\end{enumerate}%1) 2) ....
	\item%Lösung zu Aufgabe d)
	Um den Ausdruck zu formulieren, der die selbe Sprache beschreibt, wie der DEA, müssen alle Teilausdrücke $R^{(3)}_{ij}$ für alle $i\in q_{0}$ und 			$j\in F$ (alle Ausdrücke die vom Startzustand zu einem akzeptierenden Zustand führen) vereinigt werden. Das betrifft bei diesem DEA nur jenen 					Ausdruck, der von Zustand 1($q_{0}$) zu Zustand 3 ($q_{2}$) führt. Genauer:\newline\newline

	$R_{DEA} = R^{(3)}_{13}$\newline\newline

	Also muss noch der Ausdruck $R^{(3)}_{13}$ gebildet werden:\\\\
	\begin{tabbing}
	$R^{(3)}_{13} $\=$= R^{(2)}_{13} + R^{(2)}_{13}(R^{(2)}_{33})^{\ast}R^{(2)}_{33}$\\
	\>$= 1 + 0(00)^{\ast}1 + 0(00)^{\ast}01 + (\varepsilon + 11 + 0(00)^{\ast}1 + 0(00)^{\ast}01 + 10(00)^{\ast}1 + 10(00)^{\ast}01)^{\ast}$\\
	\>$= 1 + 0(00)^{\ast}1 + 0(00)^{\ast}01  + (11 + 0(00)^{\ast}1 + 0(00)^{\ast}01 + 10(00)^{\ast}1 + 10(00)^{\ast}01)^{\ast}$\\
	\>$= 1 + 0(00)^{\ast}(1 + 01) + (11 + 0(00)^{\ast}(1+01) + 10(00)^{\ast}(1 + 01))^{\ast}$\\
	\>$= 1 + 0(00)^{\ast}(1 + 01) + (11 + (0(00)^{\ast} + 10(00)^{\ast})(1 + 01))^{\ast}$
	\end{tabbing}
	
	
	\item%Lösung zu Aufgabe e)
	Der Graph des DEA sieht wie folgt aus:
	\begin{center}
%-----------------------------------------------------------------------------------------------------------
    \unitlength=4pt
    \begin{picture}(20, 14)(0,-7)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    %\node[Nmarks=ifr](C)(75,-30){all}
    \node[Nmarks=i,iangle=180](A1)(-20,0){$q_{1}$}
    \node(A2)(0,0){$q_{2}$}
    \node[Nmarks=r](A3)(20,0){$q_{3}$}
    \drawedge(A1,A2){$0$}
    \drawedge(A2,A1){$0$}
    \drawedge(A2,A3){$1$}
    \drawedge(A3,A2){$0$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(A1,A3){$1$}
    \drawedge(A3,A1){$1$}
    %\drawloop[loopangle=90](A1){$1$}
    %\drawloop[loopangle=0](A3){$0$}
    \end{picture}
%----------------------------------
	\end{center}
	Auf den Übergangspfeilen des DEAs stehen im Moment noch Zeichenreihen. Diese werden als erstes in reguläre Ausdrücke umgeschrieben. Danach sieht der 		DEA mit regulären Ausdrücken auf den Pfeilen wie folgt aus\emph{reguläre Ausdrücke seien hier mal fett gedruckt}:
	\begin{center}
	\unitlength=4pt
    \begin{picture}(20, 14)(0,-7)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    %\node[Nmarks=ifr](C)(75,-30){all}
    \node[Nmarks=i,iangle=180](A1)(-20,0){$q_{1}$}
    \node(A2)(0,0){$q_{2}$}
    \node[Nmarks=r](A3)(20,0){$q_{3}$}
    \drawedge(A1,A2){$\textbf{0}$}
    \drawedge(A2,A1){$\textbf{0}$}
    \drawedge(A2,A3){$\textbf{1}$}
    \drawedge(A3,A2){$\textbf{0}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(A1,A3){$\textbf{1}$}
    \drawedge(A3,A1){$\textbf{1}$}
    %\drawloop[loopangle=90](A1){$1$}
    %\drawloop[loopangle=0](A3){$0$}
   \end{picture}
	\end{center}
\end{enumerate}%enumeration für a) b) c) ...

Man beachte, dass der reguläre Ausdruck, der die Zeichenkette bestehend aus $\{a\}$ beschreibt, $\textbf{a}$ lautet. Deshalb hat sich am Graphen selbst nichts geändert. Um nun den Zustand $q_{2}$ zu eliminieren werden wie im Buch beschrieben, die r. Audrücke die zum Zustand $q_{2}$ führen (seien \textbf{a}), die vom Zustand $q_{2}$ zu sich selbst führen (seien \textbf{b}) und die, die vom Zustand weg führen (seien \textbf{c}) aneinander gereiht, in der Form \textbf{abc}. Da es noch Pfade gibt, die genau in die andere Richtung verlaufen, muss das ganze auch von $q_{3}$ nach $q_{1}$ in der Gegenrichtung gemacht werden. Dies führt zu dem folgenden Übergangsgraphen:

	\begin{center}
	\unitlength=4pt
    \begin{picture}(20, 14)(0,-7)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=1}
    \thinlines
    %\node[Nmarks=ifr](C)(75,-30){all}
    \node[Nmarks=i,iangle=180](A1)(-20,0){$q_{1}$}
    %\node(A2)(0,0){$q_{2}$}
    \node[Nmarks=r](A3)(20,0){$q_{3}$}
    %\drawedge(A1,A2){$\textbf{0}$}
    %\drawedge(A2,A1){$\textbf{0}$}
    %\drawedge(A2,A3){$\textbf{1}$}
    %\drawedge(A3,A2){$\textbf{0}$}
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(A1,A3){$\textbf{1 +01}$}
    \drawedge(A3,A1){$\textbf{1 + 00}$}
    %\drawloop[loopangle=90](A1){$1$}
    %\drawloop[loopangle=0](A3){$0$}
   \end{picture}
	\end{center}
Aus diesem Graphen lässt sich leicht ein Ausdruck formulieren, der die selbe Sprache beschreibt, wie der DEA: Man muss mindestens einmal von $q_{1}$ nach $q_{3}$ kommen. Von da an kann man beliebig oft (auch 0 mal) zurück zu $q_{1}$ und von dort aus wieder zu $q_{3}$. Das ergibt den folgenden Ausdruck:\\
\begin{equation}
	(1+01)((1 + 00)(1 + 01))^{\ast}
\end{equation}
\end{document}